{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "文件io"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "该文本会写入文件中看到我吧!\n"
     ]
    }
   ],
   "source": [
    "#写文件\n",
    "with open (\"test.txt\",\"wt\") as out_file:\n",
    "    out_file.write(\"该文本会写入文件中看到我吧!\")\n",
    "#Read a file \n",
    "with open (\"test.txt\", \"rt\") as in_file:\n",
    "    text = in_file.read()\n",
    "\n",
    "print(text)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字符串判断"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "测试实例\n",
      "False\n",
      "False\n",
      "False\n",
      "True\n",
      "False\n",
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(\"测试实例\")\n",
    "str = \"runoob.com\"\n",
    "print(str.isalnum()) #判断所有字符都是数字或者字母\n",
    "print(str.isalpha()) #判断所有的字符都是字母\n",
    "print(str.isdigit()) #判断所有的字符都是数字\n",
    "print(str.islower()) #判断所有的字符都是小写\n",
    "print(str.isupper()) #判断所有的字符都是大写\n",
    "print(str.isupper()) #判断所有单词都是首字母大写，像标题\n",
    "print(str.isspace()) #判断所有字符都是空白字符、\\t、\\n、\\r\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字符串大小写转换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "WWW.RUNOOB.COM\n",
      "www.runoob.com\n",
      "Www.runoob.com\n",
      "Www.Runoob.Com\n"
     ]
    }
   ],
   "source": [
    "str = \"www.runoob.com\"\n",
    "print(str.upper()) #把所有的字符中小写的字母转换成大写字母\n",
    "print(str.lower()) #把所有的字符中的大写字母转换成小写字母\n",
    "print(str.capitalize()) #把第一个字母转化成大写字母，其余为小写\n",
    "print(str.title()) #把每个单词的第一个字母转化为大写，其余为小写"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "约瑟夫生者死者小游戏"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9号下船了\n",
      "18号下船了\n",
      "27号下船了\n",
      "6号下船了\n",
      "16号下船了\n",
      "26号下船了\n",
      "7号下船了\n",
      "19号下船了\n",
      "30号下船了\n",
      "12号下船了\n",
      "24号下船了\n",
      "8号下船了\n",
      "22号下船了\n",
      "5号下船了\n",
      "23号下船了\n"
     ]
    }
   ],
   "source": [
    "#30 个人在一条船上，超载，需要 15 人下船。\n",
    "#于是人们排成一队，排队的位置即为他们的编号。\n",
    "#报数，从 1 开始，数到 9 的人下船。\n",
    "#如此循环，直到船上仅剩 15 人为止，问都有哪些编号的人下船了呢？\n",
    "people={}\n",
    "for x in range(1,31):\n",
    "    people[x]=1\n",
    "# print(people)\n",
    "check=0\n",
    "i=1\n",
    "j=0\n",
    "while i<=31:\n",
    "    if i == 31:\n",
    "        i=1\n",
    "    elif j == 15:\n",
    "        break\n",
    "    else:\n",
    "        if people[i] == 0:\n",
    "            i+=1\n",
    "            continue\n",
    "        else:\n",
    "            check+=1\n",
    "            if check == 9:\n",
    "                people[i]=0\n",
    "                check = 0\n",
    "                print(\"{}号下船了\".format(i))\n",
    "                j+=1\n",
    "            else:\n",
    "                i+=1\n",
    "                continue"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "五人分鱼"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "总共有3121条鱼\n"
     ]
    }
   ],
   "source": [
    "#A、B、C、D、E 五人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉。\n",
    "#日上三杆，A 第一个醒来，他将鱼分为五份，把多余的一条鱼扔掉，拿走自己的一份。\n",
    "#B 第二个醒来，也将鱼分为五份，把多余的一条鱼扔掉拿走自己的一份。 。\n",
    "#C、D、E依次醒来，也按同样的方法拿鱼。\n",
    "#问他们至少捕了多少条鱼?\n",
    "def main():\n",
    "    fish = 1\n",
    "    while True:\n",
    "        total, enough = fish, True\n",
    "        for _ in range(5):\n",
    "            if (total - 1) % 5 == 0:\n",
    "                total = (total - 1)  //  5 * 4\n",
    "            else:\n",
    "                enough = False\n",
    "                break\n",
    "        if enough:\n",
    "            print(f'总共有{fish}条鱼')\n",
    "            break\n",
    "        fish += 1\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "实现秒表功能"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "清空列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "清空前： [6, 4, 1]\n",
      "清空后： []\n"
     ]
    }
   ],
   "source": [
    "RUNOOB = [6,4,1]\n",
    "print('清空前：' , RUNOOB)\n",
    "\n",
    "RUNOOB.clear()\n",
    "print('清空后：',RUNOOB)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "清楚列表中重复元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 6]\n"
     ]
    }
   ],
   "source": [
    "list_1 = [1,2,1,4,6,6]\n",
    "\n",
    "print(list(set(list_1)))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "查找列表中最小元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最小元素为: 2\n"
     ]
    }
   ],
   "source": [
    "#示例一\n",
    "list1 = [10, 2, 4, 45, 99]\n",
    " \n",
    "list1.sort()\n",
    " \n",
    "print(\"最小元素为:\", *list1[:1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最小元素为: 0\n"
     ]
    }
   ],
   "source": [
    "#示例二\n",
    "list1 = [10, 20, 1, 0, 99]\n",
    " \n",
    "print(\"最小元素为:\", min(list1))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "查找列表中最大元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最大元素为: 45\n"
     ]
    }
   ],
   "source": [
    "#示例一\n",
    "list1 = [10, 20, 4, 45, 9]\n",
    " \n",
    "list1.sort()\n",
    " \n",
    "print(\"最大元素为:\", list1[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最大元素为: 99\n"
     ]
    }
   ],
   "source": [
    "#示例二\n",
    "list1 = [10, 20, 1, 45, 99]\n",
    " \n",
    "print(\"最大元素为:\", max(list1))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将字符串作为代码执行"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "def exec_code(): \n",
    "    LOC = \"\"\" \n",
    "def factorial(num): \n",
    "    fact=1 \n",
    "    for i in range(1,num+1): \n",
    "        fact = fact*i \n",
    "    return fact \n",
    "print(factorial(5)) \n",
    "\"\"\"\n",
    "    exec(LOC) \n",
    " \n",
    "exec_code()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字符串翻转"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "boonuR\n"
     ]
    }
   ],
   "source": [
    "#示例一\n",
    "str='Runoob'\n",
    "print(str[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "boonuR\n"
     ]
    }
   ],
   "source": [
    "#示例二\n",
    "str='Runoob'\n",
    "print(''.join(reversed(str)))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对字符串切片及翻转"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "头部切片翻转 :  noobRu\n",
      "尾部切片翻转 :  obRuno\n"
     ]
    }
   ],
   "source": [
    "def rotate(input,d): \n",
    "  \n",
    "    Lfirst = input[0 : d] \n",
    "    Lsecond = input[d :] \n",
    "    Rfirst = input[0 : len(input)-d] \n",
    "    Rsecond = input[len(input)-d : ] \n",
    "  \n",
    "    print( \"头部切片翻转 : \", (Lsecond + Lfirst) )\n",
    "    print( \"尾部切片翻转 : \", (Rsecond + Rfirst) )\n",
    " \n",
    "if __name__ == \"__main__\": \n",
    "    input = 'Runoob'\n",
    "    d=2  # 截取两个字符\n",
    "    rotate(input,d)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按键（key）或值（value）对字典进行排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "按键(key)排序:\n",
      "(1, 2) (2, 56) (3, 323) (4, 24) (5, 12) (6, 18) "
     ]
    }
   ],
   "source": [
    "#按键（key）排序\n",
    "def dictionairy():  \n",
    "  \n",
    "    # 声明字典\n",
    "    key_value ={}     \n",
    " \n",
    "    # 初始化\n",
    "    key_value[2] = 56       \n",
    "    key_value[1] = 2 \n",
    "    key_value[5] = 12 \n",
    "    key_value[4] = 24\n",
    "    key_value[6] = 18      \n",
    "    key_value[3] = 323 \n",
    " \n",
    "    print (\"按键(key)排序:\")   \n",
    " \n",
    "    # sorted(key_value) 返回重新排序的列表\n",
    "    # 字典按键排序\n",
    "    for i in sorted (key_value) : \n",
    "        print ((i, key_value[i]), end =\" \") \n",
    "  \n",
    "def main(): \n",
    "    # 调用函数\n",
    "    dictionairy()              \n",
    "      \n",
    "# 主函数\n",
    "if __name__==\"__main__\":      \n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "按值(value)排序:\n",
      "[(1, 2), (5, 12), (6, 18), (4, 24), (2, 56), (3, 323)]\n"
     ]
    }
   ],
   "source": [
    "#按值（value）排序\n",
    "def dictionairy():  \n",
    " \n",
    "    # 声明字典\n",
    "    key_value ={}     \n",
    " \n",
    "    # 初始化\n",
    "    key_value[2] = 56       \n",
    "    key_value[1] = 2 \n",
    "    key_value[5] = 12 \n",
    "    key_value[4] = 24\n",
    "    key_value[6] = 18      \n",
    "    key_value[3] = 323 \n",
    " \n",
    " \n",
    "    print (\"按值(value)排序:\")   \n",
    "    print(sorted(key_value.items(), key = lambda kv:(kv[1], kv[0])))     \n",
    "   \n",
    "def main(): \n",
    "    dictionairy()             \n",
    "      \n",
    "if __name__==\"__main__\":       \n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "列表通过 age 升序排序: \n",
      "[{'name': 'Runoob', 'age': 7}, {'name': 'Taobao', 'age': 100}, {'name': 'Google', 'age': 100}, {'name': 'Wiki', 'age': 200}]\n",
      "\n",
      "列表通过 age 和 name 排序: \n",
      "[{'name': 'Runoob', 'age': 7}, {'name': 'Google', 'age': 100}, {'name': 'Taobao', 'age': 100}, {'name': 'Wiki', 'age': 200}]\n",
      "\n",
      "列表通过 age 降序排序: \n",
      "[{'name': 'Wiki', 'age': 200}, {'name': 'Taobao', 'age': 100}, {'name': 'Google', 'age': 100}, {'name': 'Runoob', 'age': 7}]\n"
     ]
    }
   ],
   "source": [
    "#字典1列表排序\n",
    "lis = [{ \"name\" : \"Taobao\", \"age\" : 100},  \n",
    "{ \"name\" : \"Runoob\", \"age\" : 7 }, \n",
    "{ \"name\" : \"Google\", \"age\" : 100 }, \n",
    "{ \"name\" : \"Wiki\" , \"age\" : 200 }] \n",
    "  \n",
    "# 通过 age 升序排序\n",
    "print (\"列表通过 age 升序排序: \")\n",
    "print (sorted(lis, key = lambda i: i['age']) )\n",
    "  \n",
    "print (\"\\r\") \n",
    "  \n",
    "# 先按 age 排序，再按 name 排序\n",
    "print (\"列表通过 age 和 name 排序: \")\n",
    "print (sorted(lis, key = lambda i: (i['age'], i['name'])) )\n",
    "  \n",
    "print (\"\\r\") \n",
    "  \n",
    "# 按 age 降序排序\n",
    "print (\"列表通过 age 降序排序: \")\n",
    "print (sorted(lis, key = lambda i: i['age'],reverse=True) )"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "移除字典点键值（key/value）对"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#使用del移除\n",
    "test_dict = {\"Runoob\" : 1, \"Google\" : 2, \"Taobao\" : 3, \"Zhihu\" : 4} \n",
    "  \n",
    "# 输出原始的字典\n",
    "print (\"字典移除前 : \" + str(test_dict)) \n",
    "  \n",
    "# 使用 del 移除 Zhihu\n",
    "del test_dict['Zhihu'] \n",
    "  \n",
    "# 输出移除后的字典\n",
    "print (\"字典移除后 : \" + str(test_dict)) \n",
    "  \n",
    "# 移除没有的 key 会报错\n",
    "#del test_dict['Baidu']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#使用pop（）移除\n",
    "test_dict = {\"Runoob\" : 1, \"Google\" : 2, \"Taobao\" : 3, \"Zhihu\" : 4} \n",
    "  \n",
    "# 输出原始的字典\n",
    "print (\"字典移除前 : \" + str(test_dict)) \n",
    "  \n",
    "# 使用 pop 移除 Zhihu\n",
    "removed_value = test_dict.pop('Zhihu') \n",
    "  \n",
    "# 输出移除后的字典\n",
    "print (\"字典移除后 : \" + str(test_dict)) \n",
    "  \n",
    "print (\"移除的 key 对应的 value 为 : \" + str(removed_value)) \n",
    "  \n",
    "print ('\\r') \n",
    "  \n",
    "# 使用 pop() 移除没有的 key 不会发生异常，我们可以自定义提示信息\n",
    "removed_value = test_dict.pop('Baidu', '没有该键(key)') \n",
    "  \n",
    "# 输出移除后的字典\n",
    "print (\"字典移除后 : \" + str(test_dict)) \n",
    "print (\"移除的值为 : \" + str(removed_value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#使用items（）移除\n",
    "test_dict = {\"Runoob\" : 1, \"Google\" : 2, \"Taobao\" : 3, \"Zhihu\" : 4} \n",
    "  \n",
    "# 输出原始的字典\n",
    "print (\"字典移除前 : \" + str(test_dict)) \n",
    "  \n",
    "# 使用 pop 移除 Zhihu\n",
    "new_dict = {key:val for key, val in test_dict.items() if key != 'Zhihu'} \n",
    "  \n",
    "  \n",
    "# 输出移除后的字典\n",
    "print (\"字典移除后 : \" + str(new_dict))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "合并字典"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "{'d': 6, 'c': 4, 'a': 10, 'b': 8}\n"
     ]
    }
   ],
   "source": [
    "#使用update()方法，第二个参数合并第一个参数\n",
    "def Merge(dict1, dict2): \n",
    "    return(dict2.update(dict1)) \n",
    "      \n",
    "# 两个字典\n",
    "dict1 = {'a': 10, 'b': 8} \n",
    "dict2 = {'d': 6, 'c': 4} \n",
    "  \n",
    "# 返回  None \n",
    "print(Merge(dict1, dict2)) \n",
    "  \n",
    "# dict2 合并了 dict1\n",
    "print(dict2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 10, 'b': 8, 'd': 6, 'c': 4}\n"
     ]
    }
   ],
   "source": [
    "#使用**，函数将参数以字典的形式导入\n",
    "def Merge(dict1, dict2): \n",
    "    res = {**dict1, **dict2} \n",
    "    return res \n",
    "      \n",
    "# 两个字典\n",
    "dict1 = {'a': 10, 'b': 8} \n",
    "dict2 = {'d': 6, 'c': 4} \n",
    "dict3 = Merge(dict1, dict2) \n",
    "print(dict3)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二分查找\n",
    "\n",
    "二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "元素在数组中的索引为 3\n"
     ]
    }
   ],
   "source": [
    "# 返回 x 在 arr 中的索引，如果不存在返回 -1\n",
    "def binarySearch (arr, l, r, x): \n",
    "  \n",
    "    # 基本判断\n",
    "    if r >= l: \n",
    "  \n",
    "        mid = int(l + (r - l)/2)\n",
    "  \n",
    "        # 元素整好的中间位置\n",
    "        if arr[mid] == x: \n",
    "            return mid \n",
    "          \n",
    "        # 元素小于中间位置的元素，只需要再比较左边的元素\n",
    "        elif arr[mid] > x: \n",
    "            return binarySearch(arr, l, mid-1, x) \n",
    "  \n",
    "        # 元素大于中间位置的元素，只需要再比较右边的元素\n",
    "        else: \n",
    "            return binarySearch(arr, mid+1, r, x) \n",
    "  \n",
    "    else: \n",
    "        # 不存在\n",
    "        return -1\n",
    "  \n",
    "# 测试数组\n",
    "arr = [ 2, 3, 4, 10, 40 ] \n",
    "x = 10\n",
    "  \n",
    "# 函数调用\n",
    "result = binarySearch(arr, 0, len(arr)-1, x) \n",
    "  \n",
    "if result != -1: \n",
    "    print (\"元素在数组中的索引为 %d\" % result )\n",
    "else: \n",
    "    print (\"元素不在数组中\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "线性查找\n",
    "\n",
    "线性查找指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "元素在数组中的索引为 3\n"
     ]
    }
   ],
   "source": [
    "def search(arr, n, x): \n",
    "  \n",
    "    for i in range (0, n): \n",
    "        if (arr[i] == x): \n",
    "            return i \n",
    "    return -1 \n",
    "  \n",
    "# 在数组 arr 中查找字符 D\n",
    "arr = [ 'A', 'B', 'C', 'D', 'E' ] \n",
    "x = 'D' \n",
    "n = len(arr) \n",
    "result = search(arr, n, x) \n",
    "if(result == -1): \n",
    "    print(\"元素不在数组中\") \n",
    "else: \n",
    "    print(\"元素在数组中的索引为\", result)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "快速排序\n",
    "\n",
    "快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。\n",
    "步骤为：\n",
    "挑选基准值：从数列中挑出一个元素，称为\"基准\"（pivot）;\n",
    "分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;\n",
    "递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。\n",
    "递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。\n",
    "\n",
    "选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "排序后的数组:\n",
      "1\n",
      "5\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "def partition(arr,low,high): \n",
    "    i = ( low-1 )         # 最小元素索引\n",
    "    pivot = arr[high]     \n",
    "  \n",
    "    for j in range(low , high): \n",
    "  \n",
    "        # 当前元素小于或等于 pivot \n",
    "        if   arr[j] <= pivot: \n",
    "          \n",
    "            i = i+1 \n",
    "            arr[i],arr[j] = arr[j],arr[i] \n",
    "  \n",
    "    arr[i+1],arr[high] = arr[high],arr[i+1] \n",
    "    return ( i+1 ) \n",
    "  \n",
    " \n",
    "# arr[] --> 排序数组\n",
    "# low  --> 起始索引\n",
    "# high  --> 结束索引\n",
    "  \n",
    "# 快速排序函数\n",
    "def quickSort(arr,low,high): \n",
    "    if low < high: \n",
    "  \n",
    "        pi = partition(arr,low,high) \n",
    "  \n",
    "        quickSort(arr, low, pi-1) \n",
    "        quickSort(arr, pi+1, high) \n",
    "  \n",
    "arr = [10, 7, 8, 9, 1, 5] \n",
    "n = len(arr) \n",
    "quickSort(arr,0,n-1) \n",
    "print (\"排序后的数组:\") \n",
    "for i in range(n): \n",
    "    print (\"%d\" %arr[i]),"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "冒泡排序\n",
    "\n",
    "冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢\"浮\"到数列的顶端。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "排序后的数组:\n",
      "11\n",
      "12\n",
      "22\n",
      "25\n",
      "34\n",
      "64\n",
      "90\n"
     ]
    }
   ],
   "source": [
    "def bubbleSort(arr):\n",
    "    n = len(arr)\n",
    " \n",
    "    # 遍历所有数组元素\n",
    "    for i in range(n):\n",
    " \n",
    "        # Last i elements are already in place\n",
    "        for j in range(0, n-i-1):\n",
    " \n",
    "            if arr[j] > arr[j+1] :\n",
    "                arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    " \n",
    "arr = [64, 34, 25, 12, 22, 11, 90]\n",
    " \n",
    "bubbleSort(arr)\n",
    " \n",
    "print (\"排序后的数组:\")\n",
    "for i in range(len(arr)):\n",
    "    print (\"%d\" %arr[i]),"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "归并排序\n",
    "\n",
    "归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。\n",
    "分治法:\n",
    "分割：递归地把当前序列平均分割成两半。\n",
    "集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "给定的数组\n",
      "12\n",
      "11\n",
      "13\n",
      "5\n",
      "6\n",
      "7\n",
      "\n",
      "\n",
      "排序后的数组\n",
      "5\n",
      "6\n",
      "7\n",
      "11\n",
      "12\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "def merge(arr, l, m, r): \n",
    "    n1 = m - l + 1\n",
    "    n2 = r- m \n",
    "  \n",
    "    # 创建临时数组\n",
    "    L = [0] * (n1)\n",
    "    R = [0] * (n2)\n",
    "  \n",
    "    # 拷贝数据到临时数组 arrays L[] 和 R[] \n",
    "    for i in range(0 , n1): \n",
    "        L[i] = arr[l + i] \n",
    "  \n",
    "    for j in range(0 , n2): \n",
    "        R[j] = arr[m + 1 + j] \n",
    "  \n",
    "    # 归并临时数组到 arr[l..r] \n",
    "    i = 0     # 初始化第一个子数组的索引\n",
    "    j = 0     # 初始化第二个子数组的索引\n",
    "    k = l     # 初始归并子数组的索引\n",
    "  \n",
    "    while i < n1 and j < n2 : \n",
    "        if L[i] <= R[j]: \n",
    "            arr[k] = L[i] \n",
    "            i += 1\n",
    "        else: \n",
    "            arr[k] = R[j] \n",
    "            j += 1\n",
    "        k += 1\n",
    "  \n",
    "    # 拷贝 L[] 的保留元素\n",
    "    while i < n1: \n",
    "        arr[k] = L[i] \n",
    "        i += 1\n",
    "        k += 1\n",
    "  \n",
    "    # 拷贝 R[] 的保留元素\n",
    "    while j < n2: \n",
    "        arr[k] = R[j] \n",
    "        j += 1\n",
    "        k += 1\n",
    "  \n",
    "def mergeSort(arr,l,r): \n",
    "    if l < r: \n",
    "  \n",
    "        \n",
    "        m = int((l+(r-1))/2)\n",
    "  \n",
    "       \n",
    "        mergeSort(arr, l, m) \n",
    "        mergeSort(arr, m+1, r) \n",
    "        merge(arr, l, m, r) \n",
    "  \n",
    "  \n",
    "arr = [12, 11, 13, 5, 6, 7] \n",
    "n = len(arr) \n",
    "print (\"给定的数组\") \n",
    "for i in range(n): \n",
    "    print (\"%d\" %arr[i]), \n",
    "  \n",
    "mergeSort(arr,0,n-1) \n",
    "print (\"\\n\\n排序后的数组\") \n",
    "for i in range(n): \n",
    "    print (\"%d\" %arr[i]),"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "堆排序\n",
    "\n",
    "堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "排序后\n",
      "5\n",
      "6\n",
      "7\n",
      "11\n",
      "12\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "def heapify(arr, n, i): \n",
    "    largest = i  \n",
    "    l = 2 * i + 1     # left = 2*i + 1 \n",
    "    r = 2 * i + 2     # right = 2*i + 2 \n",
    "  \n",
    "    if l < n and arr[i] < arr[l]: \n",
    "        largest = l \n",
    "  \n",
    "    if r < n and arr[largest] < arr[r]: \n",
    "        largest = r \n",
    "  \n",
    "    if largest != i: \n",
    "        arr[i],arr[largest] = arr[largest],arr[i]  # 交换\n",
    "  \n",
    "        heapify(arr, n, largest) \n",
    "  \n",
    "def heapSort(arr): \n",
    "    n = len(arr) \n",
    "  \n",
    "    # Build a maxheap. \n",
    "    for i in range(n, -1, -1): \n",
    "        heapify(arr, n, i) \n",
    "  \n",
    "    # 一个个交换元素\n",
    "    for i in range(n-1, 0, -1): \n",
    "        arr[i], arr[0] = arr[0], arr[i]   # 交换\n",
    "        heapify(arr, i, 0) \n",
    "  \n",
    "arr = [ 12, 11, 13, 5, 6, 7] \n",
    "heapSort(arr) \n",
    "n = len(arr) \n",
    "print (\"排序后\") \n",
    "for i in range(n): \n",
    "    print (\"%d\" %arr[i]),"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计数排序\n",
    "\n",
    "计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "字符数组排序 bcmnoooruwww\n"
     ]
    }
   ],
   "source": [
    "def countSort(arr): \n",
    "  \n",
    "    output = [0 for i in range(256)] \n",
    "  \n",
    "    count = [0 for i in range(256)] \n",
    "  \n",
    "    ans = [\"\" for _ in arr] \n",
    "  \n",
    "    for i in arr: \n",
    "        count[ord(i)] += 1\n",
    "  \n",
    "    for i in range(256): \n",
    "        count[i] += count[i-1] \n",
    "  \n",
    "    for i in range(len(arr)): \n",
    "        output[count[ord(arr[i])]-1] = arr[i] \n",
    "        count[ord(arr[i])] -= 1\n",
    "  \n",
    "    for i in range(len(arr)): \n",
    "        ans[i] = output[i] \n",
    "    return ans  \n",
    "  \n",
    "arr = \"wwwrunoobcom\"\n",
    "ans = countSort(arr) \n",
    "print ( \"字符数组排序 %s\"  %(\"\".join(ans)) )"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "希尔排序\n",
    "\n",
    "希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。\n",
    "希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录\"基本有序\"时，再对全体记录进行依次直接插入排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "排序前:\n",
      "12\n",
      "34\n",
      "54\n",
      "2\n",
      "3\n",
      "\n",
      "排序后:\n",
      "2\n",
      "3\n",
      "12\n",
      "34\n",
      "54\n"
     ]
    }
   ],
   "source": [
    "def shellSort(arr): \n",
    "  \n",
    "    n = len(arr)\n",
    "    gap = int(n/2)\n",
    "  \n",
    "    while gap > 0: \n",
    "  \n",
    "        for i in range(gap,n): \n",
    "  \n",
    "            temp = arr[i] \n",
    "            j = i \n",
    "            while  j >= gap and arr[j-gap] >temp: \n",
    "                arr[j] = arr[j-gap] \n",
    "                j -= gap \n",
    "            arr[j] = temp \n",
    "        gap = int(gap/2)\n",
    "  \n",
    "arr = [ 12, 34, 54, 2, 3] \n",
    "  \n",
    "n = len(arr) \n",
    "print (\"排序前:\") \n",
    "for i in range(n): \n",
    "    print(arr[i]), \n",
    "  \n",
    "shellSort(arr) \n",
    "  \n",
    "print (\"\\n排序后:\") \n",
    "for i in range(n): \n",
    "    print(arr[i]),"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "bee83357d0ee372d886bbe8a8a0e8cb106ff43bc5de717badced2c88766a99e9"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
